<!DOCTYPE html><html><head>
<title>pt::pegrammar - Parser Tools</title>
<style type="text/css"><!--
    HTML {
	background: 	#FFFFFF;
	color: 		black;
    }
    BODY {
	background: 	#FFFFFF;
	color:	 	black;
    }
    DIV.doctools {
	margin-left:	10%;
	margin-right:	10%;
    }
    DIV.doctools H1,DIV.doctools H2 {
	margin-left:	-5%;
    }
    H1, H2, H3, H4 {
	margin-top: 	1em;
	font-family:	sans-serif;
	font-size:	large;
	color:		#005A9C;
	background: 	transparent;
	text-align:		left;
    }
    H1.doctools_title {
	text-align: center;
    }
    UL,OL {
	margin-right: 0em;
	margin-top: 3pt;
	margin-bottom: 3pt;
    }
    UL LI {
	list-style: disc;
    }
    OL LI {
	list-style: decimal;
    }
    DT {
	padding-top: 	1ex;
    }
    UL.doctools_toc,UL.doctools_toc UL, UL.doctools_toc UL UL {
	font:		normal 12pt/14pt sans-serif;
	list-style:	none;
    }
    LI.doctools_section, LI.doctools_subsection {
	list-style: 	none;
	margin-left: 	0em;
	text-indent:	0em;
	padding: 	0em;
    }
    PRE {
	display: 	block;
	font-family:	monospace;
	white-space:	pre;
	margin:		0%;
	padding-top:	0.5ex;
	padding-bottom:	0.5ex;
	padding-left:	1ex;
	padding-right:	1ex;
	width:		100%;
    }
    PRE.doctools_example {
	color: 		black;
	background: 	#f5dcb3;
	border:		1px solid black;
    }
    UL.doctools_requirements LI, UL.doctools_syntax LI {
	list-style: 	none;
	margin-left: 	0em;
	text-indent:	0em;
	padding:	0em;
    }
    DIV.doctools_synopsis {
	color: 		black;
	background: 	#80ffff;
	border:		1px solid black;
	font-family:	serif;
	margin-top: 	1em;
	margin-bottom: 	1em;
    }
    UL.doctools_syntax {
	margin-top: 	1em;
	border-top:	1px solid black;
    }
    UL.doctools_requirements {
	margin-bottom: 	1em;
	border-bottom:	1px solid black;
    }
--></style>
</head>
<!-- Generated from file 'pt_peg_introduction.man' by tcllib/doctools with format 'html'
   -->
<!-- Copyright &amp;copy; 2009 Andreas Kupries &amp;lt;andreas_kupries@users.sourceforge.net&amp;gt;
   -->
<!-- pt::pegrammar.n
   -->
<body><hr> [
   <a href="../../../../../../../../home">Tcllib Home</a>
&#124; <a href="../../../../toc.html">Main Table Of Contents</a>
&#124; <a href="../../../toc.html">Table Of Contents</a>
&#124; <a href="../../../../index.html">Keyword Index</a>
&#124; <a href="../../../../toc0.html">Categories</a>
&#124; <a href="../../../../toc1.html">Modules</a>
&#124; <a href="../../../../toc2.html">Applications</a>
 ] <hr>
<div class="doctools">
<h1 class="doctools_title">pt::pegrammar(n) 1 tcllib &quot;Parser Tools&quot;</h1>
<div id="name" class="doctools_section"><h2><a name="name">Name</a></h2>
<p>pt::pegrammar - Introduction to Parsing Expression Grammars</p>
</div>
<div id="toc" class="doctools_section"><h2><a name="toc">Table Of Contents</a></h2>
<ul class="doctools_toc">
<li class="doctools_section"><a href="#toc">Table Of Contents</a></li>
<li class="doctools_section"><a href="#synopsis">Synopsis</a></li>
<li class="doctools_section"><a href="#section1">Description</a></li>
<li class="doctools_section"><a href="#section2">Formal definition</a></li>
<li class="doctools_section"><a href="#section3">References</a></li>
<li class="doctools_section"><a href="#section4">Bugs, Ideas, Feedback</a></li>
<li class="doctools_section"><a href="#keywords">Keywords</a></li>
<li class="doctools_section"><a href="#category">Category</a></li>
<li class="doctools_section"><a href="#copyright">Copyright</a></li>
</ul>
</div>
<div id="synopsis" class="doctools_section"><h2><a name="synopsis">Synopsis</a></h2>
<div class="doctools_synopsis">
<ul class="doctools_requirements">
<li>package require <b class="pkgname">Tcl 8.5</b></li>
</ul>
</div>
</div>
<div id="section1" class="doctools_section"><h2><a name="section1">Description</a></h2>
<p>Are you lost ?
Do you have trouble understanding this document ?
In that case please read the overview provided by the
<i class="term"><a href="pt_introduction.html">Introduction to Parser Tools</a></i>. This document is the
entrypoint to the whole system the current package is a part of.</p>
<p>Welcome to the introduction to <i class="term"><a href="../../../../index.html#parsing_expression_grammar">Parsing Expression Grammar</a></i>s
(short: <i class="term"><a href="../../../../index.html#peg">PEG</a></i>), the formalism used by the Parser Tools.
It is assumed that the reader has a basic knowledge of parsing theory,
i.e. <i class="term">Context-Free Grammars</i> (short: <i class="term"><a href="../../../../index.html#cfg">CFG</a></i>),
<i class="term">languages</i>, and associated terms like <i class="term"><a href="../../../../index.html#ll_k_">LL(k)</a></i>,
<i class="term">LR(k)</i>, <i class="term"><a href="../../../../index.html#terminal">terminal</a></i> and <i class="term">nonterminal</i> <i class="term">symbols</i>,
etc.
We do not intend to recapitulate such basic definitions or terms like
<i class="term">useful</i>, <i class="term">reachable</i>, (left/right) <i class="term">recursive</i>,
<i class="term">nullable</i>, first/last/follow sets, etc.
Please see the <span class="sectref"><a href="#section3">References</a></span> at the end instead if you are in
need of places and books which provide such background information.</p>
<p>PEGs are formally very similar to CFGs, with terminal and nonterminal
symbols, start symbol, and rules defining the structure of each
nonterminal symbol.
The main difference lies in the choice(sic!) of <i class="term">choice</i>
operators. Where CFGs use an <i class="term">unordered choice</i> to represent
alternatives PEGs use <i class="term">prioritized choice</i>. Which is fancy way
of saying that a parser has to try the first alternative first and can
try the other alternatives if only if it fails for the first, and so
on.</p>
<p>On the CFG side this gives rise to LL(k) and LR(k) for making the
choice <i class="term">deterministic</i> with a bounded <i class="term">lookahead</i> of k
terminal symbols, where LL is in essence <i class="term">topdown</i> aka
<i class="term"><a href="../../../../index.html#recursive_descent">recursive descent</a></i> parsing, and LR <i class="term">bottomup</i> aka
<i class="term">shift reduce</i> parsing.</p>
<p>On the PEG side we can parse input with recursive descent and
<i class="term">backtracking</i> of failed choices, the latter of which amounts to
unlimited lookahead.
By additionally recording the success or failure of nonterminals at
the specific locations they were tried at and reusing this information
after backtracking we can avoid the exponential blowup of running time
usually associated with backtracking and keep the parsing linear. The
memory requirements are of course higher due to this cache, as we are
trading space for time.</p>
<p>This is the basic concept behind <i class="term">packrat parsers</i>.</p>
<p>A limitation pure PEGs share with LL(k) CFGs is that
<i class="term">left-recursive</i> grammars cannot be parsed, with the associated
recursive descent parser entering an infinite recursion.
This limitation is usually overcome by extending pure PEGs with
explicit operators to specify repetition, zero or more, and one or
more, or, formally spoken, for the <i class="term">kleene closure</i> and
<i class="term">positive kleene closure</i>.
This is what the Parser Tools are doing.</p>
<p>Another extension, specific to Parser Tools, is a set of operators
which map more or less directly to various character classes built
into Tcl, i.e. the classes reachable via <b class="cmd">string is</b>.</p>
<p>The remainder of this document consists of the formal definition of
PEGs for the mathematically inclined, and an appendix listing
references to places with more information on PEGs specifically, and
parsing in general.</p>
</div>
<div id="section2" class="doctools_section"><h2><a name="section2">Formal definition</a></h2>
<p>For the mathematically inclined, a Parsing Expression Grammar is a
4-tuple (VN,VT,R,eS) where</p>
<ul class="doctools_itemized">
<li><p>VN is a set of <i class="term">nonterminal symbols</i>,</p></li>
<li><p>VT is a set of <i class="term">terminal symbols</i>,</p></li>
<li><p>R is a finite set of rules, where each rule is a pair (A,e), A in VN,
and <i class="term"><a href="../../../../index.html#e">e</a></i> a <i class="term"><a href="../../../../index.html#parsing_expression">parsing expression</a></i>.</p></li>
<li><p>eS is a parsing expression, the <i class="term">start expression</i>.</p></li>
</ul>
<p>Further constraints are</p>
<ul class="doctools_itemized">
<li><p>The intersection of VN and VT is empty.</p></li>
<li><p>For all A in VT exists exactly one pair (A,e) in R. In other words, R
is a function from nonterminal symbols to parsing expressions.</p></li>
</ul>
<p>Parsing expressions are inductively defined via</p>
<ul class="doctools_itemized">
<li><p>The empty string (epsilon) is a parsing expression.</p></li>
<li><p>A terminal symbol <i class="term">a</i> is a parsing expression.</p></li>
<li><p>A nonterminal symbol <i class="term">A</i> is a parsing expression.</p></li>
<li><p><i class="term">e1</i><i class="term">e2</i> is a parsing expression for parsing expressions
<i class="term">e1</i> and <i class="term">2</i>. This is called <i class="term">sequence</i>.</p></li>
<li><p><i class="term">e1</i>/<i class="term">e2</i> is a parsing expression for parsing expressions
<i class="term">e1</i> and <i class="term">2</i>. This is called <i class="term">ordered choice</i>.</p></li>
<li><p><i class="term"><a href="../../../../index.html#e">e</a></i>* is a parsing expression for parsing expression
<i class="term"><a href="../../../../index.html#e">e</a></i>. This is called <i class="term">zero-or-more repetitions</i>, also known
as <i class="term">kleene closure</i>.</p></li>
<li><p><i class="term"><a href="../../../../index.html#e">e</a></i>+ is a parsing expression for parsing expression
<i class="term"><a href="../../../../index.html#e">e</a></i>. This is called <i class="term">one-or-more repetitions</i>, also known
as <i class="term">positive kleene closure</i>.</p></li>
<li><p>!<i class="term"><a href="../../../../index.html#e">e</a></i> is a parsing expression for parsing expression
<i class="term">e1</i>. This is called a <i class="term">not lookahead predicate</i>.</p></li>
<li><p>&amp;<i class="term"><a href="../../../../index.html#e">e</a></i> is a parsing expression for parsing expression
<i class="term">e1</i>. This is called an <i class="term">and lookahead predicate</i>.</p></li>
</ul>
<p>PEGs are used to define a grammatical structure for streams of symbols
over VT. They are a modern phrasing of older formalisms invented by
Alexander Birham. These formalisms were called TS (TMG recognition
scheme), and gTS (generalized TS). Later they were renamed to TPDL
(Top-Down Parsing Languages) and gTPDL (generalized TPDL).</p>
<p>They can be easily implemented by recursive descent parsers with
backtracking. This makes them relatives of LL(k) Context-Free
Grammars.</p>
</div>
<div id="section3" class="doctools_section"><h2><a name="section3">References</a></h2>
<ol class="doctools_enumerated">
<li><p><a href="http://www.pdos.lcs.mit.edu/~baford/packrat/">The Packrat Parsing and Parsing Expression Grammars Page</a>,
by Bryan Ford, Massachusetts Institute of Technology. This is the main
entry page to PEGs, and their realization through Packrat Parsers.</p></li>
<li><p><a href="http://en.wikipedia.org/wiki/Parsing_expression_grammar">http://en.wikipedia.org/wiki/Parsing_expression_grammar</a>
Wikipedia's entry about Parsing Expression Grammars.</p></li>
<li><p><a href="http://www.cs.vu.nl/~dick/PTAPG.html">Parsing Techniques - A Practical Guide </a>, an online book
offering a clear, accessible, and thorough discussion of many
different parsing techniques with their interrelations and
applicabilities, including error recovery techniques.</p></li>
<li><p><a href="http://scifac.ru.ac.za/compilers/">Compilers and Compiler Generators</a>, an online book using
CoCo/R, a generator for recursive descent parsers.</p></li>
</ol>
</div>
<div id="section4" class="doctools_section"><h2><a name="section4">Bugs, Ideas, Feedback</a></h2>
<p>This document, and the package it describes, will undoubtedly contain
bugs and other problems.
Please report such in the category <em>pt</em> of the
<a href="http://core.tcl.tk/tcllib/reportlist">Tcllib Trackers</a>.
Please also report any ideas for enhancements you may have for either
package and/or documentation.</p>
<p>When proposing code changes, please provide <em>unified diffs</em>,
i.e the output of <b class="const">diff -u</b>.</p>
<p>Note further that <em>attachments</em> are strongly preferred over
inlined patches. Attachments can be made by going to the <b class="const">Edit</b>
form of the ticket immediately after its creation, and then using the
left-most button in the secondary navigation bar.</p>
</div>
<div id="keywords" class="doctools_section"><h2><a name="keywords">Keywords</a></h2>
<p><a href="../../../../index.html#ebnf">EBNF</a>, <a href="../../../../index.html#ll_k_">LL(k)</a>, <a href="../../../../index.html#peg">PEG</a>, <a href="../../../../index.html#tdpl">TDPL</a>, <a href="../../../../index.html#context_free_languages">context-free languages</a>, <a href="../../../../index.html#expression">expression</a>, <a href="../../../../index.html#grammar">grammar</a>, <a href="../../../../index.html#matching">matching</a>, <a href="../../../../index.html#parser">parser</a>, <a href="../../../../index.html#parsing_expression">parsing expression</a>, <a href="../../../../index.html#parsing_expression_grammar">parsing expression grammar</a>, <a href="../../../../index.html#push_down_automaton">push down automaton</a>, <a href="../../../../index.html#recursive_descent">recursive descent</a>, <a href="../../../../index.html#state">state</a>, <a href="../../../../index.html#top_down_parsing_languages">top-down parsing languages</a>, <a href="../../../../index.html#transducer">transducer</a></p>
</div>
<div id="category" class="doctools_section"><h2><a name="category">Category</a></h2>
<p>Parsing and Grammars</p>
</div>
<div id="copyright" class="doctools_section"><h2><a name="copyright">Copyright</a></h2>
<p>Copyright &copy; 2009 Andreas Kupries &lt;andreas_kupries@users.sourceforge.net&gt;</p>
</div>
</div></body></html>
